/**
 * Description:
 * User:岁亮亮
 * Date:2025-03-11
 * TIME:10:39
 */
public class AVLTree {

    static class TreeNode{
        int value;
        int bf;
        TreeNode left;
        TreeNode right;
        TreeNode parent;
        public TreeNode(int value){
            this.value = value;
        }
    }

    TreeNode root;

    public boolean insert(int value){
        TreeNode newNode = new TreeNode(value);
        if(root == null){
            root = newNode;
            return true;
        }
        TreeNode cur = root;
        TreeNode parent = null;
        while(cur != null){
            if(cur.value > value){
                parent = cur;
                cur = cur.left;
            }
            else if(cur.value < value){
                parent = cur;
                cur = cur.right;
            }
            else {
                return false;
            }
        }
        if(parent.value < value){
            parent.right = newNode;
        }
        else {
            parent.left = newNode;
        }
        //修改插入节点的父亲节点
        //AVL树每插入一个元素都要对每颗子树的平衡因子的范围做出判断是否要对树的结构做出调整
        //从插入节点开始依次向上遍历,根据平衡因子做出判断是否调整树的结构保证高度平衡;
        cur = newNode;
        while(parent != null){
            //cur 代表插入的节点 parent 代表插入节点的父亲节点
            //插入完后调整平衡因子
            if(parent.left == cur){
                parent.bf--;
            }
            else {
                parent.bf++;
            }
            //根据插入后调整的平衡因子判断是否是高度的二叉树,不是的话调正树的结构
            if(parent.bf == 0){
                //bf == 0 时说明这个子树是平衡的, 整棵树也是平很的
                break;
            }
            //bf == -1 或者是 1 的话只能说明这个子树是平衡的 但整棵树可能不是平很的
            //这能再向上调整 看这棵树是否真的平衡
            else if(parent.bf == 1 || parent.bf == -1){
                cur = parent;
                parent = parent.parent;
            }
            else{
                if(parent.bf == 2){
                    //左旋
                    if(parent.right.bf == 1){
                        rotateLeft(parent);
                    }
                    //右左双旋
                    else if(parent.right.bf == -1){
                          rotateRL(parent);
                          break;
                    }
                }
                else if(parent.bf == -2){
                    if(parent.left.bf == 1){
                        rotateLR(parent);
                        break;

                    }
                    //右旋
                    else if(parent.right.bf == -1){
                        rotateRight(parent);
                        break;
                    }
                }
            }
        }
        return true;
    }

    private void rotateRL(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;
        int bf = subRL.bf;
        rotateLeft(subR);
        rotateRight(parent);
        if(bf == -1){
            subRL.bf = 0;
            subR.bf = 1;
            parent.bf = 0;
        }
        else if(bf == 1){
            subRL.bf = 0;
            subR.bf = 0;
            parent.bf = -1;
        }
    }

    private void rotateLR(TreeNode parent) {
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;
        int bf = subLR.bf;
        rotateLeft(subL);
        rotateRight(parent);
        if(bf == -1){
            subLR.bf = 0;
            subL.bf = 0;
            parent.bf = 1;
        }
        else if(bf == 1){
            subLR.bf = 0;
            subL.bf = -1;
            parent.bf = 0;
        }
    }

    private void rotateRight(TreeNode parent){
        TreeNode subL = parent.left;
        subL.right = parent;
        //必须先记录调整节点的父节点的父节点
        TreeNode treeParent = parent.parent;
        parent.parent = subL;
        //如果subL有右节点的话
        TreeNode subLR = subL.right;
        parent.left = subLR;
        //调正subLR的父亲节点 但先判断subLR是否存在
        if(subLR != null){
            subLR.parent = parent;
        }
        //判断parent 是否有父节点 没有就是根节点 有的话判断是它的左节点还是右节点
        if(treeParent == null){
            root = subL;
            root.parent = null;
        }
        else if(treeParent.left == parent){
            treeParent.left = subL;
            subL.parent = treeParent;
        }
        else {
            treeParent.right = subL;
            subL.parent = treeParent;
        }
        //修改调整完后的平衡因子
        subL.bf = 0;
        parent.bf = 0;

    }

    private void rotateLeft(TreeNode parent){
        TreeNode subR = parent.right;
        subR.left = parent;
        //必须先记录调整节点的父节点的父节点
        TreeNode treeParent = parent.parent;
        parent.parent = subR;
        //如果subR有左节点的话
        TreeNode subRL = subR.left;
        parent.right = subRL;
        //调正subRL的父亲节点 但先判断subLR是否存在
        if(subRL != null){
            subRL.parent = parent;
        }
        //判断parent 是否有父节点 没有就是根节点 有的话判断是它的左节点还是右节点
        if(treeParent == null){
            root = subR;
            root.parent = null;
        }
        else if(treeParent.left == parent){
            treeParent.left = subR;
            subR.parent = treeParent;
        }
        else {
            treeParent.right = subR;
            subR.parent = treeParent;
        }
        //修改调整完后的平衡因子
        subR.bf = 0;
        parent.bf = 0;
    }
}
